package Solutions;

/**
 * @Classname LongestPalindrome
 * @Description TODO
 * @Date 2021/3/2 16:28
 * @Created by ASUS
 */
public class LongestPalindrome {
    public String longestPalindrome(String str) {
        if (str == null) return null;// if str is null then just return the null value.
        if (str.length() < 2) return str;// a str that with the length less than 2 must be palindrome.
        int maxLength = 0;// record the max length of the palindrome.
        int start = 0;// record the start index of the palindrome with the max length.
        boolean[][] dp = new boolean[str.length()][str.length()];
        for (int i = 0; i < dp.length; i++) dp[i][i] = true;// init the arrays.
        for (int j = 1; j < dp.length; j++) {
            for (int i = 0; i < j; i++) {
                if (str.charAt(i) == str.charAt(j)) {
                    if (j - i < 3) {// (j-1) - (i+1) + 1 < 2
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                    if (dp[i][j] && maxLength < j - i + 1) {
                        start = i;
                        maxLength = j - i + 1;
                    }
                }
            }
        }

        return str.substring(start, start + maxLength);
    }

    public static void main(String[] args) {
        System.out.println(new LongestPalindrome().longestPalindrome("affwffa"));
    }
}
